



		NUMERE DE TELEFON - SOLUTIE
	       -----------------------------

(data de Dumitru Bogdan)

	Aceasta problema a urmarit sa testeze cunostintele de programare
dinamica ale concurentilor, precum si abilitatea de a manipula structuri
mari de date (de ordinul sutelor de KB).
	Cele maxim 50.000 de cuvinte de maxim 50 de caractere fiecare nu
puteau fi memorate intr-un vector de pointeri la string-uri, din simplul
motiv ca ar fi fost necesari 50000*50=2.500.000 octeti, adica peste 2.400
KB de memorie. Nici listele nu reprezentau o solutie, o "legatura" intre 2
celule ocupand 4 octeti.
	Singura solutie de memorare era o matrice de caractere, in care
cuvintele erau scrise "la rand". Solutia se bazeaza pe faptul ca lungimea
totala a cuvintelor nu depasea 300.000. In plus, trebuia retinut un vector
de 50.000 de elemente, care sa contina lungimile cuvintelor. Aparent, meto-
da prezinta multe dezavantaje, ca de exemplu faptul ca accesarea unui cuvant
oarecare nu se poate face decat dupa ce se calculeaza "deplasamentul" lui
fata de prima celula din matrice, nemaivorbid de faptul ca respectivul cu-
vant s-ar putea sa ocupe mai multe linii din matrice. De fapt, algoritmul
descris mai jos va folosi eficient aceasta matrice.
	Metoda de rezolvare este urmatoarea: pentru fiecare pozitie din nu-
marul de telefon retinem numarul minim de cuvinte cu care putem sa codificam
numarul pana la respectiva pozitie, precum si ultimul cuvant folosit (pentru
reconstituire). Baleiem numarul de telefon si, din pozitia curenta, incercam
sa optimizam, folosind toate cuvintele avute, obtinute baleind matricea cre-
ata. Algoritmul este o varianta de programare dinamica, cunoscuta sub numele
de "metoda inapoi". Daca reusim sa ajungem la ultima pozitie, exista solutie;
in caz contrar,nu.
	Procedura Load citeste cuvintele date si le memoreaza in matrice. Am
ales ca matricea sa aiba 30 de linii a cate 10.000 de caractere fiecare. Astfel,
un cuvant se va afla pe cel mult 2 linii ale matricei.
	Procedure Init_OK initializeaza matricea OK, utilizata pentru a testa
daca este posibila sau nu codificarea unei anumite cifre printr-un anumit ca-
racter.
	Procedura Init initializeaza vectorul V (in V[i] retinem numarul minim
de cuvinte folosite pentru a codifica subsirul format cu primele i cifre din
numarul de telefon).
	Procedura Work inearca, avand solutia optima pentru primele i cifre,
sa completeze solutia cu toate cuvintele avute. Acestea sunt considerate pe
rand (citind matricea) si testate cu ajutorul matricei OK. Daca un anumit
cuvant se potriveste, se face actualizarea.
	Procedura Imposibil determina daca problema nu are solutie, caz in care
scrie un mesaj corespunzator si suspenda executia programului.
	Procedura Reconst reconstituie solutia, procedeu deloc banal. Mai intai
se determina numerele de ordine ale cuvintelor folosite (in vectorul USE), apoi
acestea se sorteaza (in vectorul CUSE).
	In procedura Scrie se baleiaza matricea de cuvinte; cand se gaseste un
cuvant care a fost folosit in obtinerea solutiei, acesta este scris in fisierul
de iesire.
	Pentru fiecare din cele maxim 100 de cifre ale numarului de telefon, se
baleiaza matricea de cuvinte, a carei dimensiune este cel mult 300.000. Comple-
xitatea poate fi astfel O(Numarul_de_cifre * Input). 